package com.lz;

/**
 * 练兵场，leetcode
 */
public class TrialDemo {
    public static void main(String[] args) {
        TrialDemo trialDemo = new TrialDemo();
        int i = trialDemo.majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2});
        System.out.println(i);

    }

    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int majorityElemeec(int[] nums, int lo, int hi) {
        // base case; the only element in an array of size 1 is the majority
        // element.
        if (lo == hi) {
            return nums[lo];
        }

        // recurse on left and right halves of this slice.
        int mid = (hi - lo) / 2 + lo;
        int left = majorityElemeec(nums, lo, mid);
        int right = majorityElemeec(nums, mid + 1, hi);

        // if the two halves agree on the majority element, return it.
        // 1半
        if (left == right) {
            return left;
        }

        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount > rightCount ? left : right;
    }

    public int majorityElement(int[] nums) {
        return majorityElemeec(nums, 0, nums.length - 1);
    }




    int doRotting(int[][] grid, int x, int y, boolean isR) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[x].length) return 0;
        // 本次也是腐烂的
        if (isR && grid[x][y] == 2) return -1;
        grid[x][y] = 3;
        int i = doRotting(grid, x, y - 1, true);
        int i1 = doRotting(grid, x, y + 1, true);
        int i2 = doRotting(grid, x - 1, y, true);
        int i3 = doRotting(grid, x + 1, y, true);
        int max = max(i, i1, i2, i3);

        return max + 1;


    }

    int max(int i, int j, int x, int y) {
        return Integer.max(Integer.max(Integer.max(i, j), x), y);
    }

}
